package com.practice.bfs;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Stack;

public class KPeg {
	public void move(int N, int K, int[] begin, int[] end) {
		long s0 = stateToLong(begin);
		long sn = stateToLong(end);
		
		ArrayList<Node> visited = new ArrayList<Node>();
		visited.add(new Node(s0, 0, 0, -1));
		
		Deque<Integer> dq = new ArrayDeque<Integer>();
		dq.add(0);
		
		while (!dq.isEmpty()) {
			int current = dq.remove();
			for (int i=0; i<K; i++) {
				for (int j=0; j<K; j++) {
					long next = move(visited.get(current).state, i, j);
					if (next == sn) {
						visited.add(new Node(next, i+1, j+1, current));
						printSolution(visited, current);
						return;
					}
					
					if (next > 0 && !seen(visited, next)) {
						visited.add(new Node(next, i+1, j+1, current));
						dq.add(visited.size() - 1);
					}
				}
			}
		}
	}
	
	private boolean seen(ArrayList<Node> visited, long state) {
		for (Node node : visited) if (node.state == state) return true;
		return false;
	}
	
	private long stateToLong(int[] state) {
		long s = 0;
		for (int i=0; i<state.length; i++) {
			s |= (1 << i) << (8*state[i] - 8);
		}
		return s;
	}
	
	private long move(long state, int from, int to) {
		if (from == to) return -1;
		int pegFrom = (int) ((state >> 8*from) & 0xff);
		int pegTo = (int) ((state >> 8*to) & 0xff);
		for (int i=0; i<8; i++) {
			if ((pegFrom >> i & 1) > 0) {
				state &= ~((1L << i) << 8*from);
				state |= (1L << i) << 8*to;
				return state;
			}
			if ((pegTo >> i & 1) > 0) return -1;
		}
		return -1;
	}
	
	private void printSolution(ArrayList<Node> visited, int current) {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(visited.size()-1);
		while (current > 0) {
			stack.push(current);
			current = visited.get(current).parent;
		}
		System.out.println(stack.size());
		while (!stack.isEmpty()) {
			int t = stack.pop();
			System.out.println(visited.get(t).from + " " + visited.get(t).to);
		}
	}
	
	private class Node {
		long state;
		int from;
		int to;
		int parent;
		public Node(long state, int from, int to , int parent) {
			this.state = state;
			this.from = from;
			this.to = to;
			this.parent = parent;
		}
	}
	
	public static void main(String[] args) {
		KPeg k = new KPeg();
//		k.move(2, 3, new int[]{1, 1}, new int[]{2, 2});
		k.move(6, 4, new int[]{4, 2, 4, 3, 1, 1}, new int[]{1, 1, 1, 1, 1, 1});
	}
}
